#pragma once
#include<iostream>
using namespace std;


enum Colour {
	RED,
	BLACK
};

template <class Value>
struct RBTreeNode {
	RBTreeNode<Value>* _left;
	RBTreeNode<Value>* _right;
	RBTreeNode<Value>* _parent;

	Colour _Col;

	Value _Val;

	RBTreeNode(const Value& val)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _Col(RED)
		, _Val(val)
	{}
};


//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator {
	typedef Ref reference; //结点指针的引用
	typedef Ptr pointer; //结点指针

	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> Self;

	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*() {
		return _node->_Val;
	}

	Ptr operator->() {
		return &_node->_Val;
	}

	bool operator!=(const Self& s)const {
		return _node != s._node;
	}

	bool operator==(const Self& s)const {
		return _node == s._node;
	}

	Self& operator++() {
		//如果当前节点右子树不为空
		//那么就访问右子树的最左节点
		if (_node->_right) {
			Node* left = _node->_right;

			while (left->_left) {
				left = left->_left;
			}

			_node = left;
		}
		//当前节点的右子树为空
		else {
			Node* cur = _node;
			Node* parent = cur->_parent;

			//当前节点是父亲节点的右节点
			//说明当前节点的父亲节点也已经访问完
			//继续向上迭代
			while (parent && parent->_right == cur) {
				cur = parent;
				parent = parent->_parent;
			}

			//此时说明当前节点是父亲节点的左节点，下一个就该访问父亲节点了
			_node = parent;
		}

		return *this;
	}


	Self& operator--() {
		if (_node->_left) {
			Node* right = _node->_left;
			while (right->_right) {
				right = right->_right;
			}

			_node = right;
		}
		else {
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent && parent->_left == cur) {
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

};


template<class Iterator>
struct ReverseIterator {
	typedef ReverseIterator<Iterator> Self;
	typedef typename Iterator::reference Ref;
	typedef typename Iterator::pointer Ptr;


	Iterator _it;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

	Ref operator*() {
		return *_it;
	}

	Ptr operator->() {
		return _it.operator->();
	}

	Self& operator++() {
		--_it;
		return *this;
	}

	Self& operator--() {
		++_it;
		return *this;
	}

	bool operator!=(const Self& s) {
		return _it != s._it;
	}

	bool operator==(const Self& s) {
		return _it == s._it;
	}
};



template <class Key, class Val, class KeyOfValue>
class RBTree {
	typedef RBTreeNode<Val> Node;
public:
	typedef __TreeIterator<Val, Val&, Val*> iterator;  //正向迭代器
	typedef ReverseIterator<iterator> reverse_iterator;//反向迭代器


	RBTree()
		:_root(nullptr)
	{}
	~RBTree() {
		_Destroy(_root);
	}


	iterator begin() {
		Node* left = _root;

		while (left && left->_left) {
			left = left->_left;
		}

		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	reverse_iterator rbegin() {
		Node* right = _root;

		while (right && right->_right) {
			right = right->_right;
		}

		return reverse_iterator(right);
	}

	reverse_iterator rend()
	{
		return reverse_iterator(nullptr);
	}



	pair<iterator, bool> Insert(const Val& val) {

		KeyOfValue kov;

		//先按照二叉搜索树的插入方式把节点插入到红黑树

		//根节点为空
		if (_root == nullptr) {
			_root = new Node(val);
			//根节点必须是黑色
			_root->_Col = BLACK;
			return make_pair(iterator(_root), true);
		}

		//根节点不为空 

		Node* parent = nullptr;
		Node* cur = _root;

		while (cur) {
			if (kov(cur->_Val) > kov(val)) {
				parent = cur;
				cur = cur->_left;
			}
			else if (kov(cur->_Val) < kov(val)) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				//节点已经存在，插入失败
				return make_pair(iterator(cur), false);
			}
		}

		//找到要插入的节点位置
		cur = new Node(val);
		//记录插入节点的位置
		Node* newNode = cur;

		//新节点的链接关系
		if (kov(parent->_Val) > kov(val)) {
			parent->_left = cur;
			cur->_parent = parent;
		}
		else {
			parent->_right = cur;
			cur->_parent = parent;
		}
		

		//插入新节点成功

		//检测红黑树的性质是否被破坏



		//如果cur的parent存在且为红，说明树的性质已经被破坏
		while (parent && parent->_Col == RED) {
			//这时就要看cur的uncle
			Node* grandParent = parent->_parent;
			if (parent == grandParent->_left) {
				Node* uncle = grandParent->_right;

				//情况1 cur的uncle存在且为红色
				//变色处理
				if (uncle && uncle->_Col == RED) {
					parent->_Col = BLACK;
					uncle->_Col = BLACK;
					grandParent->_Col = RED;

					cur = grandParent;
					parent = cur->_parent;
				}

				//情况2 cur的uncle存在且为黑 
				//说明cur不是新增节点，cur是情况1迭代上来的
				//情况3 cur的uncle不存在 可以和情况2合并
				//进行右单旋 变色
				else{
					//祖孙三代在一条直线
					if (parent->_left == cur) {
						//右单旋
						_RotateR(grandParent);
						//变色
						parent->_Col = BLACK;
						grandParent->_Col = RED;
					}
					else { //parent->_right == cur
						//左单旋
						_RotateL(parent);

						//右单旋
						_RotateR(grandParent);
						//变色
						grandParent->_Col = RED;
						cur->_Col = BLACK;
					}

					break;
					//旋转完后，调整完成，不用再向上调整
				}
			}
			//parent == grandParent->_right
			else {
				Node* uncle = grandParent->_left;
				//uncle为红 变色
				if (uncle && uncle->_Col == RED) {
					uncle->_Col = BLACK;
					parent->_Col = BLACK;
					grandParent->_Col = RED;

					//继续向上检测
					cur = grandParent;
					parent = cur->_parent;
				}
				//uncle为黑或者uncle不存在
				else {
					//祖孙三代在一条直线
					if (parent->_right == cur) {
						//左单旋
						_RotateL(grandParent);
						//变色
						grandParent->_Col = RED;
						parent->_Col = BLACK;
					}
					//祖孙三代不在一条直线
					else {
						_RotateR(parent);
						_RotateL(grandParent);

						//变色
						grandParent->_Col = RED;
						cur->_Col = BLACK;
					}

					//旋转完结束
					break;
				}
			}
		}


		//插入成功
		//把红黑树的根节点变成黑色
		_root->_Col = BLACK;
		return make_pair(iterator(newNode), true);
	}




	Node* Find(const Key& key) {
		KeyOfValue kov;

		if (_root == nullptr)
			return nullptr;

		Node* cur = _root;

		while (cur) {
			if (kov(cur->_Val) > key) {
				cur = cur->_left;
			}
			else if (kov(cur->_Val) < key) {
				cur = cur->_right;
			}
			else {
				//找到了
				return cur;
			}
		}

		//没找到
		return nullptr;
	}


	bool IsRBTree() {
		if (_root == nullptr)
			return true;

		if (_root->_Col == RED) {
			cout << "根节点为红色" << endl;
			return false;
		}
			

		//计算一个路径黑色节点的标准值
		Node* cur = _root;

		int BlackNum = 0;

		while (cur) {
			if (cur->_Col == BLACK)
				BlackNum++;

			cur = cur->_left;
		}

		int count = 0;

		return _IsRBTree(_root, BlackNum, count);
	}

	void InOrder() {
		_InOrder(_root);
	}

private:

	void _RotateL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* grandParent = parent->_parent;

		parent->_right = subRL;
		if (subRL) {
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root) {
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			if (grandParent->_left == parent) {
				grandParent->_left = subR;
			}
			else {
				grandParent->_right = subR;
			}
			subR->_parent = grandParent;
		}
	}


	//右单旋
	void _RotateR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* grandParent = parent->_parent;

		parent->_left = subLR;
		//subLR有可能为空
		if (subLR) {
			subLR->_parent = parent;
		}

		subL->_right = parent;
		parent->_parent = subL;


		//看要旋转的点是子树还是根
		if (parent == _root) {
			_root = subL;
			subL->_parent = nullptr;
		}
		else {
			if (grandParent->_left == parent) {
				grandParent->_left = subL;
			}
			else {
				grandParent->_right = subL;
			}
			subL->_parent = grandParent;
		}

	}


	bool _IsRBTree(Node* root, int BlackNum, int count) {
		
		//找到了路径结束
		if (root == nullptr) {
			if (count != BlackNum) {
				//有一条路径黑色节点数量和最左路径不相等
				cout << "有一条路径黑色节点数量和最左路径不相等" << endl;
				return false;
			}
			return true;
		}

		//检测红色节点的父节点是否是红色节点
		if (root->_Col == RED && root->_parent->_Col == RED) {
			cout << "有两个连续的红色节点" << endl;
			return false;
		}

		//如果节点是黑色 ++count
		if (root->_Col == BLACK)
			count++;

		return _IsRBTree(root->_left, BlackNum, count)
			&& _IsRBTree(root->_right, BlackNum, count);
	}


	void _InOrder(Node* root) {
		if (root == nullptr)
			return;

		_InOrder(root->_left);

		cout << root->_kv.first << " : " << root->_kv.second << endl;
		_InOrder(root->_right);
	}


	void _Destroy(Node* root) {
		if (root == nullptr)
			return;

		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

private:
	Node* _root;
};